#define _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#include"tree.h"
typedef  BTNode* qdatatype;
typedef struct Qnode {
	struct Qnode* next;
	qdatatype data;
}Qnode;
typedef struct queue {
	int size;
	Qnode* head;
	Qnode* tail;
}queue;
void Queueinit(queue* p) {
	assert(p);
	p->head = p->tail = NULL;
	p->size = 0;
}


void Queuedestroy(queue* p) {
	assert(p);
	Qnode* cur = p->head;
	while (cur) {
		Qnode* next = cur->next;
		free(cur);
		cur = next;
	}
	p->size = 0;
	p->tail = p->head = NULL;
}
void Queuebackpush(queue* p, qdatatype x) {
	assert(p);
	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
	if (newnode == NULL) {
		perror(malloc);
		return;
	}
	newnode->next = NULL;
	newnode->data = x;
	if (p->tail == NULL) {
		p->head = p->tail = newnode;
	}
	else {
		p->tail->next = newnode;
		p->tail = newnode;
	}
	p->size++;


}
qdatatype Queuefrontdata(queue* p) {
	assert(p);
	assert(p->size > 0);
	return p->head->data;
}
bool QueueEmpty(queue* p) {
	assert(p);
	return p->size == 0;
}
void Queuefrontpop(queue* p) {
	assert(p);
	assert(p->size > 0);
	if (p->head->next == NULL) {
		free(p->head);
		p->head = p->tail = NULL;
	}
	else {
		Qnode* next = p->head->next;
		free(p->head);
		p->head = next;
	}
	p->size--;
}
BTNode* createnode(BTDataType x) {
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL) {
		perror(malloc);
		return NULL;
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) {
	
		if (a[*pi] == '#') {
			

			return NULL;
		}

		BTNode* node = createnode(a[*pi]);
		

		(*pi)++;
		node->left = BinaryTreeCreate(a, n, pi);
			(*pi)++;

		node->right = BinaryTreeCreate(a, n,pi);
	

			return node;
	
}

int BinaryTreeSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

int BinaryTreeLeafSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->left==NULL && root->right == NULL) {
		return 1;
	}
	return  BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
int BinaryTreeLevelKSize(BTNode* root, int k) {
	if (root == NULL) {
		return 0;
	}
	if (k == 1) {
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) 
		+ BinaryTreeLevelKSize(root->right, k - 1);
}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
	queue q;
	Queueinit(&q);
	Queuebackpush(&q, root);
	while (!QueueEmpty(&q)) {
		BTNode* ret = Queuefrontdata(&q);
		Queuefrontpop(&q);
		if (ret->data == x) {
			Queuedestroy(&q);
			return ret;
		}
		if (ret->left != NULL) {

			Queuebackpush(&q, ret->left);
		}
		if (ret->right != NULL) {

			Queuebackpush(&q, ret->right);
		}
	}
	
	Queuedestroy(&q);
	return NULL;


}
void BinaryTreePrevOrder(BTNode* root) {
	if (root == NULL) {
		printf("# ");
		return;
	}
	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);


}
//
void BinaryTreeInOrder(BTNode* root) {
	if (root == NULL) {
		printf("# ");
         return;
 
	}
	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
}
void BinaryTreePostOrder(BTNode* root) {
	if (root == NULL) {
		printf("# ");
         return;
 
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}
//
void BinaryTreeDestory(BTNode** root) {
	if (*root != NULL) {
		BinaryTreeDestory(&((*root)->left));
		BinaryTreeDestory(&((*root)->right));
		free(*root);
		*root=NULL;
	}
}
//
void BinaryTreeLevelOrder(BTNode* root) {
	queue q;
	Queueinit(&q);
	Queuebackpush(&q, root);
	while (!QueueEmpty(&q)) {
		BTNode*ret=Queuefrontdata(&q);
		Queuefrontpop(&q);
		printf("%c ", ret->data);
		if (ret->left!= NULL) {
			
			Queuebackpush(&q, ret->left);
		}
		if (ret->right!= NULL) {
			
			Queuebackpush(&q, ret->right);
		}
	}
	Queuedestroy(&q);

}
int BinaryTreeComplete(BTNode* root) {
	int is = 1;
	int size = 0;
	queue q;
	Queueinit(&q);
	Queuebackpush(&q, root);
	size = 1;
	BTNode* ret = NULL;
	while (!QueueEmpty(&q)) {
		ret = Queuefrontdata(&q);
		Queuefrontpop(&q);
		size--;
		if (ret != NULL) {
			Queuebackpush(&q, ret->left);
			Queuebackpush(&q, ret->right);
			size += 2;
		}
		else {
			break;
		}
		
	}
	while (size--) {
		ret = Queuefrontdata(&q);
		Queuefrontpop(&q);
		if (ret != NULL) {
			 is = 0;
			break;
		}

	}
	Queuedestroy(&q);

	return is;
}